Gra

Limit pamięci: 32 MB

Kolejny deszczowy dzień. Paweł i Gaweł znów byli zmuszeni do pozostania w domu. W związku z brakiem zajęć postanowili wymyślić jakąś grę.

Paweł wpadł na genialny pomysł. Na kartce papieru narysował pól. Na każdym polu znajdowały się dwie liczby - pierwsza z nich była numerem pola (liczba naturalna od do , pola miały parami różne numery), a druga jego wartością (liczba całkowita od do ). Na polu numer umieścił pionek. Zadaniem gracza było wykonywanie kolejnych ruchów, polegających na rzucie sześcienna kostką (z numerami od do napisanymi na ściankach) oraz przesuwaniu pionka o wskazaną liczbę oczek. Gra kończyła się, kiedy pionek stanął na pole o numerze . Wynikiem, jaki uzyskał gracz, była suma wartości pól na jakich stał pionek.

Po rozegraniu kilku partii Paweł i Gaweł otrzymali kilka różnych wyników, jednak nie wiedzieli czy któryś z nich był największym możliwym do uzyskania. Zadzwonili więc do Ciebie, utalentowanego informatyka, abyś napisał program, który dla danej planszy obliczy maksymalny możliwy do uzyskania wynik.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę pól na planszy. Drugi wiersz zawiera liczb całkowitych , , ..., (), gdzie oznacza wartość -tego pola.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą maksymalny możliwy do uzyskania wynik na danej planszy.

Przykład

Dla danych wejściowych:

4
1 2 -1 1

poprawną odpowiedzią jest:

4

Autor zadania: Dariusz Sosnowski.